<?php
/*
 * 给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
*/

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) {
        $this->val = $value;
    }
}

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val)
    {
        $this->val = $val;
    }
}

class Solution {

    /**
     * @param ListNode $head
     * @param TreeNode $root
     * @return Boolean
     */
    function isSubPath($head, $root) {
        if ($head == null) {
            return true;
        }
        if ($root == null) {
            return false;
        }
        $tree_path_list = $this->binaryTreePaths($root);
        $list_path = $this->listPath($head);
        return in_array($list_path, $tree_path_list);
    }



    function binaryTreePaths($root) {
        return $this->construct_paths($root, array(), array(), array(), false, false, true);
    }

    function construct_paths($node, $left_parent_path_list, $right_parent_path_list, $path_list, $is_left, $is_right, $is_root) {
        $symbol = '->';

        if ($is_left) {
            foreach ($left_parent_path_list as &$left_parent_path_item) {
                $path_list[] = $left_parent_path_item.$symbol.$node->val;
                if ($node->left != null || $node->right != null) {
                    $left_parent_path_item = $left_parent_path_item.$symbol.$node->val;
                }
            }
        }

        if ($is_right) {
            foreach ($right_parent_path_list as &$right_parent_path_item) {
                $path_list[] = $right_parent_path_item.$symbol.$node->val;
                if ($node->left != null || $node->right != null) {
                    $right_parent_path_item = $right_parent_path_item.$symbol.$node->val;
                }
            }
        }

        $path_list[] =  is_int($node->val) ? strval($node->val) : $node->val;

        if ($node->left) {
            if ($is_left || $is_root) {
                $left_parent_path_list[] = $node->val;
            }
            if ($is_root) {
                $path_list = $this->construct_paths($node->left, $left_parent_path_list, $right_parent_path_list, $path_list, true, false, false);
            } else {
                $path_list = $this->construct_paths($node->left, $left_parent_path_list, $right_parent_path_list, $path_list, $is_left, false, false);
            }
        }
        if ($node->right) {
            if ($is_right || $is_root) {
                $right_parent_path_list[] = $node->val;
            }
            if ($is_root) {
                $path_list = $this->construct_paths($node->right, $left_parent_path_list, $right_parent_path_list, $path_list, false, true, false);
            } else {
                $path_list = $this->construct_paths($node->right, $left_parent_path_list, $right_parent_path_list, $path_list, false, $is_right, false);
            }
        }
        return $path_list;
    }

    function listPath($head)
    {
        $symbol = '->';
        $curr = $head;
        $path = '';
        while ($curr != null) {
            $path = ($path == '') ? $curr->val : $path.$symbol.$curr->val;
            $curr = $curr->next;
        }
        return $path;
    }
}

$node_1 = new ListNode(1);
$node_2 = new ListNode(2);
$node_3 = new ListNode(3);
$node_4 = new ListNode(4);
$node_5 = new ListNode(5);
$node_1->next = $node_2;
$node_2->next = $node_3;
$node_3->next = $node_4;
$node_4->next = $node_5;

$tree_node_1 = new TreeNode(1);
$tree_node_2 = new TreeNode(2);
$tree_node_3 = new TreeNode(3);
$tree_node_4 = new TreeNode(4);
$tree_node_5 = new TreeNode(5);
$tree_node_6 = new TreeNode(6);
$tree_node_1->right = $tree_node_2;
$tree_node_2->right = $tree_node_3;
$tree_node_3->right = $tree_node_4;
$tree_node_4->right = $tree_node_5;
$tree_node_1->left = $tree_node_6;

var_dump(array_unique((new  Solution())->binaryTreePaths($tree_node_1)));
var_dump((new  Solution())->listPath($node_1));